//1、先实现插入功能（注意不能有重，否则插入失败）
//   a.插入功能实现后，计算平衡因子
//   b.平衡因子：如果变为0，则高度不变；如果变为1/-1，继续往上更新平衡因子直到root或平衡因子变为0
//   c.如果不为1/0/-1，为2/-2，直接对这部分子树进行旋转

#pragma once
#include <iostream>
#include <vector>
#include <string>
#include <assert.h>
#include<time.h>
using namespace std;

template<class K, class V>
struct AVLTreeNode {//采用的是三叉链，存储的类型为pair<K,V>
    pair<K, V> _kv;
    AVLTreeNode* _right;
    AVLTreeNode* _left;
    AVLTreeNode* _parent;
    int _bf;//设置平衡因子 balance factor

    AVLTreeNode(const pair<K, V>& kv = pair<K, V>())//默认构造
        :_kv(kv)
        , _right(nullptr)
        , _left(nullptr)
        , _parent(nullptr)
        , _bf(0)
    {}

};

template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
    //成员
public:
    pair<K, V> _kv;
    Node* _root;


public:
    AVLTree()//默认构造
        :_root(nullptr)
    {}

    AVLTree(const pair<K, V>& kv)//构造函数
        :_root(nullptr)
        , _kv(kv)
    {
        insert(kv);
    }
    int insert(const pair<K, V>& kv)
    {
        Node* cur = _root;
        Node* parent = nullptr;
        //如果AVL树中为空
        if (cur == nullptr) {//new一个节点后直接return返回
            _root = new Node(kv);
            return true;
        }
        //如果不为空
        else {
            while (cur)//只要cur不为空就一直往下走,直到cur为空时，才是要插入的位置
            {
                if (kv.first > cur->_kv.first) {//如果插入的数比cur大，就放到右边
                    parent = cur;
                    cur = cur->_right;
                }
                else if (kv.first < cur->_kv.first) {//如果插入的数比cur小，就放到左边
                    parent = cur;
                    cur = cur->_left;
                }
                else {//如果插入的数相同了，直接return false
                    return false;
                }

                //当cur为空时，可以退出循环，准备插入工作
            }
            //插入cur
            Node* newnode = new Node(kv);
            if (kv.first > parent->_kv.first) { parent->_right = newnode; }//插入在右子树时
            else if (kv.first < parent->_kv.first) { parent->_left = newnode; }//插入在左子树时
            cur = newnode;
            cur->_parent = parent;
        }
        //至此，插入完成--------------------------------------------------------------------------
        //插入后，cur是新节点，parent是新节点的父节点




        //调整平衡因子并确认是否需要单旋or双旋（最复杂的一步骤）
        while (parent)//每次修改的是parent的平衡因子，当parent为空，即cur到达root时，平衡因子调整彻底结束
        {
            if (cur == parent->_left)//如果cur是在parent节点的左边，则说明parent节点的左边加了高度，bf需要--
            {
                parent->_bf--;
            }
            else//如果在右边，则parent的bf++
            {
                parent->_bf++;
            }
            //往上判断调整平衡因子
            if (parent->_bf == 0)//当平衡因子变为0，则parent的子树高度不改变，不影响父节点的平衡因子，直接退出
            {
                return true;
            }

            else if (parent->_bf == 1 || parent->_bf == -1) //说明子树高度有变化，需要调整父节点的平衡因子
            {
                cur = cur->_parent;
                parent = parent->_parent;
                
                //将cur与parent往上找，继续
            }
            else if (parent->_bf == 2 || parent->_bf == -2)// 左右边高度不平衡
            {
                if (parent->_bf == 2 && cur->_bf == 1) //单左旋
                {
                    RotateL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == -1) //单右旋
                {
                    RotateR(parent);
                }

                //折线：当出现折线时，说明此处需要进行双旋操作才能平衡，具体看noite笔记
                else if (parent->_bf == 2 && cur->_bf == -1) {//折线点在左子树的双旋
                    int bf = cur->_left->_bf;//提前记录折线处节点的bf，用来判断修改后面的cur和parent
                    RotateRL(parent);
                    //双旋后，需要对父节点和平衡因子进行
                    if (bf == 0)//新插入的节点就是折线节点
                        return true;
                    else if (bf == -1)
                        //新插入的节点在折线节点的左边
                    {
                        parent->_bf = 0;
                        cur->_bf = 1;
                    }
                    else if (bf == 1)
                        //新插入的节点在折线节点的右边
                    {
                        parent->_bf = -1;
                        cur->_bf = 0;
                    }
                }
                else if (parent->_bf == -2 && cur->_bf == 1) //折线点在左子树的双旋
                {
                    int bf = cur->_right->_bf;
                    RotateLR(parent);
                    if (bf == 0)
                        return true;
                    else if (bf == -1)
                        //新插入的节点在折线节点的左边
                    {
                        cur->_bf = 0;
                        parent->_bf = 1;
                    }
                    else if (bf == 1)
                        //新插入的节点在折线节点的右边
                    {
                        cur->_bf = -1;
                        parent->_bf = 0;
                    }
                }
                //无论是单旋还是双旋，旋转完毕并且调整完平衡因子后都应该返回
                return true;
            }
            else //发生预料之外的情况（bug）返回错误
            {
                printf("发生未知错误，170行附近\n");
                return true;
            }
        }

    }

    void RotateLR(Node* Parent)
    {
        Node* parent = Parent;
        Node* cur = parent->_left;
        RotateL(cur);
        RotateR(parent);
    }
    void RotateRL(Node* Parent)
    {
        Node* parent = Parent;
        Node* cur = parent->_right;
        RotateR(cur);
        RotateL(parent);
    }

    void RotateL(Node* Parent)//左单旋,具体原理看notie笔记
    {
        Node* parent = Parent;
        Node* cur = parent->_right;//左单旋，cur必定是parent的右边，具体画图理解

        parent->_right = cur->_left;
        if (cur->_left) {//如果cur的左子树有节点，就将左子树的父节点从cur变为parent
            cur->_left->_parent = parent;
        }
        cur->_left = parent;
        Node* ppnode = parent->_parent;
        if (parent == _root) {//parent为根节点时：
            _root = cur;
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
        else
        {
            if (ppnode->_left == parent)//ppnode的左节点是parent
            {
                ppnode->_left = cur;
            }
            else if (ppnode->_right == parent)//ppnode的右节点是parent
            {
                ppnode->_right = cur;
            }
            parent->_parent = cur;
            cur->_parent = ppnode;
        }

        cur->_bf = 0;
        parent->_bf = 0;
    }

    void RotateR(Node* Parent)//右单旋,具体原理看notie笔记
    {
        Node* parent = Parent;
        Node* cur = parent->_left;//右单旋，cur必定是parent的左边，具体画图理解

        parent->_left = cur->_right;
        if (cur->_right) {//如果cur的右子树有节点，就将右子树的父节点从cur变为parent
            cur->_right->_parent = parent;
        }
        cur->_right = parent;
        Node* ppnode = parent->_parent;
        if (parent == _root) {//parent为根节点时：
            _root = cur;
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
        else
        {
            if (ppnode->_left == parent)//ppnode的左节点是parent
            {
                ppnode->_left = cur;
            }
            else if (ppnode->_right == parent)//ppnode的右节点是parent
            {
                ppnode->_right = cur;

            }
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
        cur->_bf = 0;
        parent->_bf = 0;
    }

    int Height(Node* root)
    {
        if(root == nullptr)
            return 0;
        int rightheight = Height(root->_right);
        int leftheight = Height(root->_left);

        return rightheight >= leftheight ? rightheight+1 : leftheight+1;
    }

    bool IsBalance()
    {
        _IsBalance(_root);
    }

    bool _IsBalance(Node* root)//判断是否AVL树
    {
        //搜刮左右子树高度然后相减，绝对值不大于1即为AVL树
        if(root == nullptr)
            return true;

        int rightheight = Height(root->_right);
        int leftheight = Height(root->_left);
        int result = rightheight - leftheight;
        //判断本身是否符合AVL树规则，同时判断两个子节点是否符合规则
        //每个子节点又会去判断自己的子节点
        return abs(result) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
    }

    bool print()
    {
        if (!_root) {
            printf("nullptr\n");
            return true;
        }
        vector<pair<K, V>> v;
        _print(_root, v);
        for (auto e : v) {
            cout << e.first << "_" << e.second << " ";
        }
        cout << endl;
        return true;
    }
    bool _print(Node* cur, vector<pair<K, V>>& v)
    {
        if (cur == nullptr)
            return true;

        _print(cur->_left,v);
        v.push_back(cur->_kv);
        _print(cur->_right,v);
        return true;
    }
};